package lc.q201_250;

import lc.TreeNode;

public class Q235 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果遇到一个比p大，比q小的，则肯定是它的祖先
        // 然后找下一个节点，左右对比，如果右节点比q大，则就是root了，而如果left比p小
        if (p.val > q.val) {
            TreeNode temp = p;
            p = q;
            q = temp;
        }

        // 二叉搜索数，如果p比root小，往左边搜，如果q比root大往右变搜，这时候就刚好不一样了，所以节点就是root
        // 优化点，首先肯定可以不用递归
        TreeNode next = root;
        while (next != null) {
            if (next.val >= p.val && next.val <= q.val) {
                return next;
            } else {
                if (next.val < p.val) {
                    next = next.right;
                } else {
                    next = next.left;
                }
            }
        }
        return next;
    }
}
